home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / cmln1084.arc / PORTC3.LTG < prev    next >
Text File  |  1986-10-01  |  6KB  |  294 lines
  1. /* - dgsx.c 
  2. Utilites to create and search reserved word tables.  In-core digital 
  3. search trees created by the 'dgsm.c' routines are compressed and all
  4. inter-node references are converted to indexes rather than absolute
  5. memory references.
  6. */
  7.  
  8. #include <stdio.h>
  9. #include "dgsdefs.h"
  10. #include "algnm.h"
  11.  
  12. static struct tblctrl *ctrl;
  13. static struct xtbctrl *xtrl;
  14. static char *base;
  15. static ALIGN u;
  16. #ifndef EXACT
  17. static int glsym;
  18. #endif
  19.  
  20. /*- CDGX.C ---------------------------------------------------------
  21. Translate an in-core tree into a compressed, index-based tree, with
  22. no 'successor' indexes.  'cdgx' allocates twice the actual size of
  23. the in-core tree to allow for allignment bytes.
  24. ------------------------------------------------------------------*/
  25. cdgx(gctrl,gxctrl)
  26. struct tblctrl *gctrl;
  27. struct xtbctrl *gxctrl;
  28. {
  29.  
  30. char *malloc();
  31. ctrl=gctrl;
  32. gxctrl->nentry=gctrl->nentry;
  33. gxctrl->depth=gctrl->depth;
  34. gxctrl->tblptr=base=u.cptr=malloc((unsigned)(2*mtrsiz(gctrl)));
  35. if(base==NULL)
  36. return(FALSE);
  37. dgx(ctrl->syptr,0);
  38. gxctrl->size=(u.cptr-base);
  39. return(TRUE);
  40. }
  41.  
  42. /* Create a compressed node.
  43.   'u' always points to the next free location. */
  44.  
  45. dgx(mptr,lvl)
  46. struct synode *mptr;
  47. int lvl;
  48. {
  49.  
  50. char *flgptr,*strcpy();
  51. struct llist *lptr;
  52. unsigned short int *laltptr;
  53. if(mptr != NULL)
  54. {
  55. if(lvl < ctrl->depth)
  56. {
  57. /* create the flag, store the node char.    */
  58. flgptr=u.cptr++;
  59. *flgptr=NULL;
  60. *u.cptr++=mptr->sym;
  61. /* store the aligned symbol #    */
  62. if(mptr->symno)
  63. {
  64. *flgptr |= SYM;
  65. *uslgn(u)=mptr->symno;
  66. u.usptr++;
  67. }
  68. /* make room for the 'alternate' index if necessary    */
  69. if(mptr->alt)
  70. {
  71. *flgptr |= ALT;
  72. laltptr=uslgn(u);
  73. u.usptr++;
  74. }
  75. if(dgx(mptr->suc,lvl+1))
  76. *flgptr |= SUC;
  77. if(*flgptr & ALT)
  78. {
  79. *laltptr=dgx(mptr->alt,lvl);
  80. }
  81. return(flgptr-base);
  82. }
  83. /* proceed into the linked list    */
  84. else
  85. {
  86. for(lptr=(struct llist *)mptr; lptr != NULL; lptr=lptr->suc)
  87. {
  88. strcpy(u.cptr,lptr->symptr);
  89. u.cptr+=(strlen(lptr->symptr)+1);
  90. *uslgn(u)=lptr->symno;
  91. u.usptr++;
  92. }
  93. *u.cptr++=NULL;
  94. return(TRUE);
  95. }
  96. }
  97. else return(NULL);
  98. }
  99.  
  100. /*- SGX.C ------------------------------------------------------------
  101. Search a compressed digital search tree.  Returned value depends on
  102. the definition of 'EXACT'.
  103. EXACT = TRUE;      return the symbol number if an exact match
  104.         is found, or NULL if not.
  105. EXACT = FALSE;    return : a) the symbol number if an exact match is
  106.                 found.
  107.              b) the negative of the symbol number if
  108.                 an inexact match is found.
  109.              c) NULL if no match is found.
  110. ---------------------------------------------------------------------*/
  111. sgx(gxtrl,c)
  112. struct xtbctrl *gxtrl;
  113. char *c;
  114. {
  115.  
  116. #ifndef EXACT
  117. int n;
  118. #endif
  119. xtrl=gxtrl;
  120. base=xtrl->tblptr;
  121.  
  122. #ifndef EXACT
  123. glsym=NULL;
  124. return((n=sx(xtrl->tblptr,c,0)) ? n : -glsym);
  125. #endif
  126.  
  127. #ifdef EXACT
  128. return(sx(xtrl->tblptr,c,0));
  129. #endif
  130. }
  131.  
  132. /* Search a compressed node    */
  133. sx(flg,c,lvl)
  134. char *flg,*c;
  135. int lvl;
  136. {
  137.  
  138. char *altptr(),*sucptr(),*ptr;
  139. int t;
  140. if(flg)
  141. {
  142. if(lvl < xtrl->depth)
  143. {
  144. if(*c < *(flg+1))
  145. return(NULL);
  146. else if(*c > *(flg+1))
  147. return(sx(altptr(flg),c,lvl));
  148. else
  149. {
  150.  
  151. #ifndef EXACT
  152. glsym=symn(flg);
  153. #endif
  154.  
  155. return(*++c != '\0' ? sx(sucptr(flg),c,lvl+1) : symn(flg));
  156. }
  157. }
  158. /* search the linked list */
  159. else
  160. {
  161. for(u.cptr=flg; *u.cptr != NULL;  )
  162. {
  163. ptr=u.cptr;
  164. u.cptr+=strlen(u.cptr)+1;
  165. uslgn(u);
  166.  
  167. #ifndef EXACT
  168. if(fndsub(ptr,c) == 0)
  169. glsym=*u.usptr;
  170. #endif
  171.  
  172. if((t=strcmp(c,ptr)) == 0)
  173. return((int) *u.usptr);
  174. else if(t < 0)
  175. return(NULL);
  176. u.usptr++;
  177. }
  178. return(NULL);
  179. }
  180. }
  181. else return(NULL);
  182. }
  183.  
  184. /* routines to extract values/pointers from a compressed node */
  185. symn(flg)
  186. char *flg;
  187. {
  188. if(*flg & SYM)
  189. {
  190. u.cptr=flg+2;
  191. return((int)*uslgn(u));
  192. }
  193. else return(NULL);
  194. }
  195.  
  196. char *altptr(flg)
  197. char *flg;
  198. {
  199. if(*flg & ALT)
  200. {
  201. u.cptr=flg+2;
  202. uslgn(u);
  203. if(*flg & SYM)
  204. u.usptr++;
  205. return(base+*u.usptr);
  206. }
  207. else return(NULL);
  208. }
  209.  
  210. char *sucptr(flg)
  211. char *flg;
  212. {
  213. if(*flg & SUC)
  214. {
  215. u.cptr=flg+2;
  216. if(*flg & SYM)
  217. {
  218. uslgn(u);
  219. u.usptr++;
  220. }
  221. if(*flg & ALT)
  222. {
  223. uslgn(u);
  224. u.usptr++;
  225. }
  226. return(u.cptr);
  227. }
  228. else return(NULL);
  229. }
  230.  
  231. /*- XPRT ---------------------------------------------------
  232. Dump a compressed digital search tree.
  233. -----------------------------------------------------------*/
  234. xprt(gxctrl)
  235. struct xtbctrl *gxctrl;
  236. {
  237.  
  238. xtrl=gxctrl;
  239. base=xtrl->tblptr;
  240. xp(xtrl->tblptr,0);
  241. }
  242.  
  243. /* print out the nodes */
  244.  
  245. xp(flg,lvl)
  246. int lvl;
  247. char *flg;
  248. {
  249.  
  250. char *sucptr(),*altptr();
  251. if(flg)
  252. {
  253. if(lvl < xtrl->depth)
  254. {
  255. u.cptr=flg;
  256. fprintf(stdout,"%d     flag: %d   char: %c",(flg-base),*flg,*(flg+1));
  257. fprintf(stdout,"   symbol #: %d   ",symn(flg));
  258. fprintf(stdout,"suc: %d  ",(sucptr(flg) ? sucptr(flg)-base : NULL));
  259. fprintf(stdout," alt: %d\n",(altptr(flg) ? altptr(flg)-base : NULL));
  260. xp(sucptr(flg),lvl+1);
  261. xp(altptr(flg),lvl);
  262. }
  263. else
  264. {
  265. for(u.cptr=flg; *u.cptr !=NULL; )
  266. {
  267. fprintf(stdout,"         %s   ",u.cptr);
  268. u.cptr+=strlen(u.cptr)+1;
  269. uslgn(u);
  270. fprintf(stdout,"%d\n",*u.usptr++);
  271. }
  272. }
  273. }
  274. }
  275.  
  276. /*--- FNDSUB ----------------------------------------------------------
  277. Return the index (i) of a substring within a string (stg[i]), or EOF
  278.     on no match.  Both strings must be null-terminated.
  279. ----------------------------------------------------------------------*/
  280. fndsub(sub,stg)
  281. char *sub,*stg;
  282. {
  283. char *ptr1,*ptr2,*base=stg;
  284. for(;;stg++)
  285. {
  286. for(ptr1=sub, ptr2=stg; *ptr1==*ptr2 && *ptr1!='\0'; ptr1++, ptr2++)
  287. ;
  288. if(*ptr1=='\0')
  289. return((int)(stg-base));
  290. else if(*ptr2=='\0')
  291. return(EOF);
  292. }
  293. }
  294.